#include <bits/stdc++.h>
using namespace std;

const int N = 1e3+5;

int n, m;

inline int trans(char ch) {
    if (ch >= 'a' && ch <= 'z') return ch - 'a';
    else if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 26;
    else return 0;
}

inline char trans2(int id) {
    if (id < 26) return 'a' + id;
    else return 'A' + id - 26;
}

void decrypt(const char a[], char b[]) {
    int lena = strlen(a), lenb = strlen(b);
    for (int i=0; i<lenb; ++i) {
        int ida = trans(a[i%lena]), idb = trans(b[i]);
        // printf("%d %d %d\n", i, ida, idb);
        b[i] = trans2((idb + 52 - ida) % 52);
    }
}

char s[N][N];

int u[N], v[N];

int main(int argc, char const *argv[])
{
    scanf("%d%d", &n, &m);
    for (int i=0; i<m; ++i) {
        scanf("%d%d", &u[i], &v[i]);
        --u[i]; --v[i];
    }
        
    for (int i=0; i<n; ++i) {
        scanf("%s", s[i]);
    }
    for (int i=m-1; i>=0; --i) {
        // puts("FUCK");
        decrypt(s[u[i]], s[v[i]]);
    }

    for (int i=0; i<n; ++i) 
        printf("%s\n", s[i]);
    return 0;
}
